package ugraph;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;

import javax.swing.text.html.HTMLDocument.Iterator;

import avp.GameConstants;

import edu.cornell.cs.cs2110.RandomBag;

public class Ship implements UGraph<Node, Edge> {
	
	private Set<Node> nodes= new HashSet<Node>();
	private Set<Edge> edges= new HashSet<Edge>();
	//make private?
	public HashMap<Node, HashSet<Node>> list= new HashMap<Node, HashSet<Node>>();  //adjacency list

	public void addNode(Node node) {
		nodes.add(node);
		//add node to adjacency list
		HashSet<Node> set= new HashSet<Node>();
		list.put(node, set);
	}

	public void removeNode(Node node) {
		nodes.remove(node);
		//remove from adjacency list
		for(Node n: list.get(node)){
			list.get(n).remove(node);
		}
		list.remove(node);
	}

	public void addEdge(Edge edge) {
		edges.add(edge);
		//add connection to adjacency list
		java.util.Iterator<Node> i= edge.getAdjacent().iterator();
		Node n1= i.next();
		Node n2= i.next();
		list.get(n1).add(n2);
		list.get(n2).add(n1);
	}

	public void removeEdge(Edge edge) {
		edges.remove(edge);
		//remove connection from adjacency list
		java.util.Iterator<Node> i= edge.getAdjacent().iterator();
		Node n1= i.next();
		Node n2= i.next();
		list.get(n1).remove(n2);
		list.get(n2).remove(n1);
	}
	
	public UGraph<Node, Edge> clone(){
		//TODO
		//copy adj matrix too?
		UGraph<Node, Edge> clone= new Ship();
		for(Node n : nodes){
			clone.addNode(n);
		}
		for(Edge e: edges){
			clone.addEdge(e);
		}
		return clone;
	}

	public Set<Node> getNodes() {
		return nodes;
	}

	public Set<Edge> getEdges() {
		return edges;
	}

	public UGraph<Node, Edge> spanningTree() {
		RandomBag<Edge> bag= new RandomBag<Edge>();
		for(Edge e: edges){
			bag.insert(e);
		}
		Ship spanTree= new Ship();
		for(Node n: nodes){
			spanTree.addNode(n);
		}
		
		HashSet<Node> connected= new HashSet<Node>();

		while(spanTree.getEdges().size() < spanTree.getNodes().size()-1){
			Edge e= bag.extract();
			java.util.Iterator<Node> i= e.getAdjacent().iterator();
			Node n1= i.next();
			Node n2= i.next();
			if(!connected.contains(n1) || !connected.contains(n2)){
				connected.add(n1);
				connected.add(n2);
				spanTree.addEdge(e);
			}
			//for connecting 2 connected components that aren't single nodes
			else if(spanTree.getPath(n1, n2)==null) spanTree.addEdge(e);
		}
		return spanTree;
	}

	public List<Edge> getPath(Node start, Node end) {
		HashMap<Node, List<Edge>> map= new HashMap<Node, List<Edge>>();
		Queue<Node> visited= new LinkedList<Node>(); //visited nodes
		boolean done= false;
		
		for(Node n: nodes){
			map.put(n, null);
		}
		
		map.put(start, new LinkedList<Edge>());
		visited.add(start);
		
		while(!done && !visited.isEmpty()){
			Node nextVertex= visited.poll();
		
			for(Node n: list.get(nextVertex)){
				if(map.get(n)==null){
					//update edges
					List<Edge> newList= new LinkedList<Edge>(); 
					newList.addAll(map.get(nextVertex));
					newList.add(edgeBetween(nextVertex, n));
					map.put(n, newList);
					//mark as visited
					visited.add(n);
					if(n.equals(end)) done= true;
				}
			}	
		}
		return map.get(end);
	}
	
	//Helper method to find the edge between two nodes.  Returns null if
	//there isn't one.
	private Edge edgeBetween (Node n1, Node n2){
		for(Edge e: n1.getAdjacent()){
			if(e.getAdjacent().contains(n2)) return e;
		}
		return null;
	}
}
